package summary;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/8 12:21
 */
public class Title264 {

    public static int nthUglyNumber(int n) {
        PriorityQueue<Long> priorityQueue = new PriorityQueue<>();
        int[] nums = {2, 3, 5};
        Set<Long> hash = new HashSet<>();
        hash.add(1L);
        priorityQueue.offer(1L);
        int result = 0;
        for (int i = 0; i < n; i++) {
            //最小的出队
            long poll = priorityQueue.poll();
            result = (int) poll;
            for (int j = 0; j < nums.length; j++) {
                //队头（丑数 2/3/5的倍数）
                long temp = poll * nums[j];
                if (hash.add(temp)) {
                    priorityQueue.offer(temp);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        nthUglyNumber(11);
    }
}
